The present invention relates to forwarding devices in general. More particularly, the present invention relates to a method and apparatus for performing longest match address lookups for routing a packet or cell of information in a network.
The popularity of communications networks such as the Internet and World Wide Web (WWW) is growing at a phenomenal rate. Part of the reason for this growth is the rich amount of content available through these networks, as well as the ability to provide interactive communications services. For example, it is currently possible to place a telephone call using the Internet rather than the Public Switched Telephone Network (PSTN). Moreover, it is possible to engage in multi-media communications over the Internet, such as video conferencing, telecontrol, distributed computer applications, multimedia conferencing, remote visualization, high definition television (HDTV) and even virtual reality.
The increase in usage of the Internet increases the basic unit of transfer used by the Internet, namely data packets. The Internet is already required to process hundreds of thousands of packets per second, with indications that it must process millions of packets per second to maintain pace with user demand. In response to this demand, communications technologies have been developed which significantly improve the number of packets which can be moved through the network.
A problem still persists, however, with a class of network devices which are integral to combining disparate networks together. These network devices are collectively referred to as forwarding devices, examples of which include packet switches, routers and bridges. The basic function of a forwarding device is exactly as it sounds, that is, the forwarding device takes a data packet, looks up forwarding information needed to route the packet to its destination, and forwards the packet to another network device using the forwarding information.
A forwarding device accomplishes this basic routing or directing function by utilizing a routing table. A routing table comprises destination addresses and forwarding information used by the forwarding device to direct a packet to its next or ultimate destination. In recent years, the sheer number of destination addresses required for the routing table have caused forwarding devices to become saturated in terms of processing power and memory allocation. Lookup algorithms designed to compare a destination address retrieved from a packet with the ever-growing number of destination address stored in the routing table are far too slow and inefficient to meet current forwarding device throughput requirements.
In an attempt to reduce the number of destination addresses required for a routing table, a new Internet addressing scheme was developed which is referred to as Classless Interdomain Routing (CIDR). CIDR aggregates or groups IP addresses together in hierarchical levels, similar to the hierarchical addressing scheme used to route a telephone call to a specific call recipient using a telephone number. Take for example the telephone number 412-555-1212. The area code (i.e., 412) indicates the general area of the call recipient, while the next three digits (e.g., 555) further narrows down the location to a more specific local, while the last four digits (i.e., 1212) identifies the precise location of the called party. CIDR groups IP addresses together in a similar hierarchical pattern, with the leftmost bits of an IP address giving the location of a particular network, while the location of a network device or host becomes increasingly specific as the address reads to the rightmost bit. For example, a typical Internet address under the IP version 4 (IPv4) addressing scheme might be 1.1.1.2 in decimal form, which is represented in binary form as a sequence of 32 binary bits, i.e., 00000001.00000001.00000001.00000010. CIDR is a method of identifying those address bits which are meaningful for routing a packet to its next destination. Since the Internet is comprised of a plurality of forwarding devices, it is sometimes unnecessary to have a complete destination address for each packet in the routing table. Rather, an abbreviated address could be used which merely represents forwarding information to the next forwarding device. This is referred to as xe2x80x9chop-by-hop forwarding.xe2x80x9d Thus, instead of using 00000001.00000001.00000001.00000010 to index forwarding information for a packet, CIDR assigns a prefix for each address, the prefix comprising an IP address and some indication of the leftmost contiguous significant bits within this address. For example, the CIDR prefix 1.1.1.2/16 would mean that only the first 16 bits of the address 1.1.1.2 are significant for routing purposes. The result is fewer destination addresses are required for each Internet forwarding device""s routing table.
Although CIDR reduced the number of destination addresses stored in a routing table, CIDR also complicated the lookup algorithms required to lookup forwarding information stored in the table. Under CIDR, routing to all destinations is always performed on a longest match basis. It may occur that a routing table may have different length prefixes of the same network which match the destination address of a packet. When a forwarding device must decide between two different length prefixes of the same network, it will always follow the longer mask. By way of analogy, if a switch in the PSTN had a choice to route a call using just the area code, or the area code and next three digits, the switch would use the area code plus three digits to route the call since it is more precise. As an example for a forwarding device, assume that a forwarding device has the following two CIDR prefixes in its routing table: (1) 198.32.1.0/24 via path 1 and (2) 198.32.0.0/16 via path 2. When trying to deliver traffic to host 198.32.1.1., the forwarding device tries to match the destination with the longest prefix and in this case would deliver the traffic via path 1. Thus, the longest match rule imposed by CIDR requires that for each destination address embedded within a packet, the lookup algorithm must search the entire routing table for the longest prefix.
The CIDR longest match rule can be better understood with reference to FIG. 1. FIG. 1 is a diagram for a logical representation of the longest match rule. A data packet is received by a forwarding device with an IP address of 124.13.7.5. The forwarding device uses a lookup algorithm to search for matching prefixes within a routing table 16. Routing table 16 contains prefixes with varying levels of granularity, with the meaningless bits represented by the letter xe2x80x9cXxe2x80x9d. The search first uncovers the matching prefix 124.X.X.X (referred to as match preference three). Since the longest match rule requires that the entire routing table be searched for the longest prefix that matches the destination address, the forwarding device must continue searching routing table 16. The continued search uncovers a second match preference of 124.13.X.X. Since the address 124.13.7.5 more closely resembles 124.13.X.X, this match preference is more desirable the match preference three since it more specifically identifies a route for the packet. Finally, the search uncovers a first match preference of 124.13.7.X. Since this prefix is the closest match to the address 124.13.7.5 in routing table 16, the forwarding device will use the forwarding information associated with this prefix to route the packet to its next destination.
Different lookup solutions such as the hash, radix tree, Patricia tree and cached variations thereof, have been developed to perform longest match lookups required by CIDR. The conventional lookup solutions, however, are unsatisfactory for a number of reasons. For example, all of the conventional solutions suffer under the fact that the number of steps necessary for a longest match lookup can grow large in certain cases. This leads to more frequent memory accesses, which slow down the lookup process. Current state of the art solutions such as Patricia trees or radix trees can degenerate to as many as 32 memory accesses per IPv4 address lookup. This is because Patricia tree or radix tree algorithms compare individual bits of a destination address with individual bits stored in the routing table. Since there are 32 bits in the destination address, there are 32 levels of bits stored in the routing table. Therefore, it is possible that each bit of the destination address must be compared with each level of the routing table if the longest match prefix happens to be at the bottom level. Since each bit comparison requires at least one memory access, a single lookup using Patricia tree or radix tree solutions could require up to 32 memory accesses for a worst case scenario. Moreover, these solutions only work for limited amount of addresses, caches have to be populated and de-populated often, and they require fairly complex lookup algorithms which further slow down forwarding device throughput.
The following example will help demonstrate the above problems. Current user demands indicate that forwarding devices need to process at least a million packets per second. A million packets per second is equivalent to 1 millisecond per packet, or 1000 nanoseconds per packet. It is desirable for forwarding devices to utilize inexpensive 60 nanosecond Dynamic Random Access Memory (DRAM) to store routing tables in order to decrease hardware costs associated with forwarding devices. Thus, every time the forwarding device needs to access a piece of data in a routing table stored in inexpensive DRAM, it takes 60 nanoseconds. Conventional lookup algorithms such as those associated with the Patricia tree solution require at least 32 memory accesses per IPv4 address lookup assuming a worst case scenario, which at 60 nanoseconds per access requires 1920 nanoseconds per packet or lookup. Consequently, forwarding devices using conventional lookup algorithms are not capable of processing one million packets per second, since this would require 1000 nanoseconds per lookup, and the best conventional lookup algorithms can only reach 1920 nanoseconds per lookup under worst case conditions.
Various techniques such as xe2x80x9cpipeliningxe2x80x9d and xe2x80x9cparallel processingxe2x80x9d have been implemented to improve the performance of conventional lookup algorithms. Even with these performance enhancing techniques, however, forwarding devices utilizing conventional lookup algorithms are not capable of reaching the desired throughput speeds without significantly increasing the cost of the forwarding device itself.
Another problem with conventional forwarding devices is the maintenance of the routing table. According to principles well-known in the art, the routing table,for a forwarding device must be periodically updated to reflect address and routing changes throughout the network. Conventional maintenance techniques, however, cannot update a routing table without preventing the forwarding device from utilizing the routing table. This is because conventional techniques read-lock those routing table entries that are currently being updated. This means that if a packet destination address requires the lookup of a routing table entry that is currently being updated, the packet will have to wait until the updating process is finished before being forwarded, or in the worst case scenario, be dropped from the network entirely.
In view of the foregoing, it can be appreciated that a substantial need exists for a innovative longest match lookup solution which solves the above-discussed problems.
One embodiment of the invention comprises a method and apparatus for forwarding packets in a network. A routing table is constructed using p-structures. An address for a packet is received. The address is matched with a longest prefix stored in the routing table. A decision value associated with the longest prefix is retrieved. The packet is forwarded in accordance with the decision value.
This embodiment of the invention matches an address with the longest stored prefix by first initializing a current partition member to a first partition member. The address is then translated into a p-structure index utilizing partition information stored for the current partition member. A decision value associated with the index is stored. A test is made to determine if there is a pointer associated with the index. If there is a pointer associated with the index, the current partition member is set to a next partition member associated with the pointer. This process is repeated until there are no more pointers associated with last index.
This embodiment of the invention translates the address into a p-structure index utilizing partition information stored for the current partition member by first storing the address in a register. A mask associated with the current partition member is then retrieved. The address is then masked with the partition mask, and shifted to the right in accordance with a shift value associated with the current partition member.
With these and other advantages and features of the invention that will become hereinafter apparent, the nature of the invention may be more clearly understood by reference to the following detailed description of the invention, the appended claims and to the several drawings attached herein.